package DataStructure.tree;

import DataStructure.tree.TreeNode;

/**
 * 543. 二叉树的直径 https://leetcode.cn/problems/diameter-of-binary-tree
 * 题目简述：给你一棵二叉树的根节点，返回该树的直径。二叉树的直径是指树中任意两个节点之间最长路径的长度 。
 */
public class DiameterOfBinaryTree {

    /**
     * 思路：二叉树的直径即为任一节点左右子树高度之和的最大值。因此通过后续遍历计算每个节点左右子树高度，然后更新maxLen
     */
    int maxLen = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        getHeight(root);
        return maxLen;
    }

    /**
     * 获取以root为根节点的树的高度，即左右子树中较高值+1
     */
    public int getHeight(TreeNode root) {
        if(root == null) return 0;
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        //以root为转折点的路径长度即为左子树高度加上右子树高度
        if(leftHeight + rightHeight > maxLen)
            maxLen = leftHeight + rightHeight;
        return Math.max(leftHeight, rightHeight) + 1;
    }
}
